package exercise;

import java.util.Arrays;

// 颜色分类
// https://leetcode.cn/problems/sort-colors/
public class L230701_II {
    public void sortColors(int[] nums) {
        // 循环不变量
        // all in [0, p1) == 0
        // all in [p1, i] == 1
        // all in (p2, len-1] == 2

        int p1 = 0;
        int p2 = nums.length - 1;
        int i = 0;

        while (i <= p2) {
            if (nums[i] == 0) {
                swap(p1, i, nums);
                p1++;
                i++;
            } else if (nums[i] == 1) {
                i++;
            } else {
                swap(i, p2, nums);
                p2--;
            }
        }
    }

    private void swap(int index1, int index2, int[] nums) {
        int tmp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = tmp;
    }


}
